package com.jhxy.algorithm.maxprofit;

/**
 * 买卖股票最佳时机:分治法
 */
public class DivideAndConquer {


    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int price = maxSubArrayProfit(prices, 0, prices.length - 1);
        return Math.max(maxProfit, price);
    }

    private int maxSubArrayProfit(int[] prices, int leftIndex, int rightIndex) {
        int arrayLength = rightIndex - leftIndex + 1;

        if (arrayLength <= 3) {
            int maxProfit = 0;

            for (int i = leftIndex; i < rightIndex; i++) {
                for (int j = leftIndex + 1; j <= rightIndex; j++) {
                    int profit = prices[j] - prices[i];
                    maxProfit = Math.max(maxProfit, profit);
                }
            }

            return maxProfit;
        }

        int midIndex = (rightIndex - leftIndex) / 2 + leftIndex;
        int rightMaxProfit = maxSubArrayProfit(prices, midIndex + 1, rightIndex);
        int leftMaxProfit = maxSubArrayProfit(prices, leftIndex, midIndex);

        int midMaxProfit = maxProfitContainsMidIndex(prices, midIndex, leftIndex, rightIndex);

        return Math.max(leftMaxProfit,Math.max(rightMaxProfit,midMaxProfit));
    }

    private int maxProfitContainsMidIndex(int[] prices, int midIndex, int leftIndex, int rightIndex) {
        int leftMin = Integer.MAX_VALUE;
        int rightMax = Integer.MIN_VALUE;

        if (leftIndex < midIndex) {
            leftMin = getMinNumber(prices, leftIndex, midIndex);
        } else if (leftIndex == midIndex) {
            leftMin = prices[midIndex];
        }

        if (rightIndex > midIndex + 1) {
            rightMax = getMaxNumber(prices, midIndex + 1, rightIndex);
        } else if (rightIndex == midIndex) {
            rightMax = prices[midIndex];
        }

        return rightMax -leftMin;
    }

    private int getMaxNumber(int[] prices, int start, int end) {
        int maxSum = Integer.MIN_VALUE;

        for (int i = start; i <= end; i++) {
            if (maxSum < prices[i]) {
                maxSum = prices[i];
            }
        }
        return maxSum;
    }

    private int getMinNumber(int[] prices, int leftIndex, int midIndex) {
        int minSum = Integer.MAX_VALUE;

        for (int i = leftIndex; i <= midIndex; i++) {
            if (minSum > prices[i]) {
                minSum = prices[i];
            }
        }
        return minSum;
    }

}
